/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/decode-string
   @Language: C++
   @Datetime: 19-05-09 14:47
   */

class Solution {
	string expand(const string &str, int start, int end){
		string res;
		for(int i=start, j=start, count=0; j<end; ++j){
			if(str[j]=='[' && count++==0) i=j;
			else if(str[j]==']'){
				if(--count) continue;
				int k=str.find_first_of("0123456789",start);
				if(k>start) res.append(str.substr(start,k-start));
				string tmp=expand(str,i+1,j);
				for(int l=atoi(str.substr(k,i-k).c_str()); l--; res.append(tmp));
				start=j+1;
			}
		}
		if(end>start) res.append(str.substr(start,end-start));
		return res;
	}
public:
	/**
	 * @param s: an expression includes numbers, letters and brackets
	 * @return: a string
	 */
	string expressionExpand(string &str) {
		// write your code here
		return expand(str,0,str.length());
	}
};
